#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

/**
 * babel 回溯 + 字符串
 */
class Solution
{
private:
    vector<string> ans;
    vector<int> tmp;

public:
    vector<string> restoreIpAddresses(string s)
    {
        if (s.size() > 12 || s.size() < 4)
        {
            return ans;
        }
        Helper(s, 0, 0);
        return ans;
    }

    string changeToIP()
    {
        return to_string(tmp[0]) + "." + to_string(tmp[1]) + "." + to_string(tmp[2]) + "." + to_string(tmp[3]);
    }

    bool validNum(string s)
    {
        if (s.size() == 0 || s.size() > 3)
        {
            return false;
        }
        if (s == "0")
        {
            return true;
        }
        if (s[0] == '0')
        {
            return false;
        }
        if (atoi(s.c_str()) >= 0 && atoi(s.c_str()) <= 255)
        {
            return true;
        }
        return false;
    }

    /**
     * @param ix 目前到哪
     * @param seg 现在有几段了
     */
    void Helper(string s, int ix,int seg)
    {
        if(seg == 4){
            string ip = changeToIP();
            ans.push_back(ip);
            return;
        }

        int num = 0;
        for(int i=ix;i<s.size();i++){
            if(s.size()-i-1 > 3*(3 - seg)){
                continue;
            }
            string tmp_s = s.substr(ix,i-ix+1);
            if(! validNum(tmp_s)){
                continue;
            }
            tmp.push_back(atoi(tmp_s.c_str()));
            Helper(s,i+1,seg+1);
            tmp.pop_back();
        }
    }
};


int main()
{
    Solution solu = Solution();
    solu.restoreIpAddresses("25525511135");
    int i = 1;
    return 0;
}
